package Main;

public class BucketSort extends Derp implements Runnable{
  //
  //test code to print out arrays so we can see what's happening,can be taken out for final product with gui
  //

  private int steps;
  private boolean sort;
  //this multidimensional array is our holder of buckets,with each row being a bucket
  private int[][] arrays;
  //inArray keeps track of how many integers we have put in the bucket
  private int[] inArrays;
  private int numbuckets;
  private int arrLen;
  private int currentBucket;
  private int currentNum;
  private int[] arr;

  public BucketSort(int arr[]){
	this.arr = arr;
    steps = 0;
    arrLen = arr.length;
    sort = false;
    //declare variables
    int max=0;
    int modmax=0;
    numbuckets=0;
    //determine max number
    for(int i = 0; i < arr.length; i++ ) {
      if(arr[i]>max){
        max=arr[i];
      }
    }
    //use max to determine number of buckets
    modmax=max%10;
    if(modmax==0){
      numbuckets=max/10;
    }
    else{
      numbuckets=(max/10)+1;
    }

    arrays = new int[numbuckets][arr.length];
    inArrays = new int[numbuckets];

    for(int i=0;i<numbuckets;i++)
    {
      inArrays[i]=0;
    }
  }
  public void run() {
    while(!bucket());
    //System.out.println(printArray(getFinalArray()));
  }
  
  public String printArray(int[] p)
  {
	  String ret="[";
	  for(int i=0;i<p.length;i++){
		  ret+=p[i]+", ";
	  }
	  ret+="]";
	  return ret;
  }
  
  public int[] getFinalArray()
  {
    int[] arr = new int[arrLen];
    //put the bucket together to form our sorted array
    int arrplace=0;//keeps track of our spot in out orignal array
    for (int r=0; r<arrays.length; r++) {
      for (int c=0; c<arrays[r].length; c++) {
        arr[arrplace]=arrays[r][c];
        arrplace++;     }

    }
    return arr;
  }

  public int[][] getBuckets(){return arrays;}
  public int[] getCurrentChange(){int[] s = {currentBucket,currentNum};return s;}

  //
  //sorts the actual buckets using a count sort, a more specific form of a bucket sort
  //
  public int [] sortbuckets(int arr2[],int threshold,int size){
    int[] arr = new int[size]; //array with the size equal to the amount of numbers in the array
    for(int i=0;i<size;i++){ // this loop sets all values from the original array to the new, smaller array
      arr[i]=arr2[i];
    }
    int arrstore[]=new int[11];//array to store the count
    int move=threshold-10;//need to alter the numbers so there within 0-10 value,we do this by subtracting the threshold
    //number, thresold would equal 10 for the 0-10 bucket,20 for the 11-20 bucket,and so on
    for(int i = 0; i < arr.length; i++ ) {
      arrstore[(arr[i]-move)]++;//count up all the numbers
    }
    //for loop to go through and transcribe the count of each number and put it back into the orignal
    //array and readjusting it by adding what we subtracted in move
    for(int i=0,j=0; i < arrstore.length; i++) {
      for(; arrstore[i]>0; (arrstore[i])--) {
        arr[j++] = i+move;
      }
    }

    return arr;
  }

  //
  //actual bucket sort
  //splits list into buckets based on intervals of 10
  //sends bucket to sortbuckets
  //puts together the buckets and returns a completed array
  //


  public boolean bucket(){

    if (steps < arr.length && !sort){ //this for loop will go through each number in the original array

      //this int sets our threshold or max number in current bucket,starts at 10
      int threshold=10;
      for(int ii = 0; ii < numbuckets; ii++ ) { //this loop goes through each bucket to see if the number belongs in it
        if(arr[steps]<=threshold&&arr[steps]>(threshold-10)){
          arrays[ii][inArrays[ii]]=arr[steps]; //place the number in the bucket
          inArrays[ii]++; //increase the amount of integers we have in the bucket
          currentBucket = ii;
          currentNum = arr[steps];
          ii=numbuckets;
        }
        //increment threshold
        threshold=threshold+10;
      }
      steps++;
    }
    else if(steps==arr.length && !sort)
    {
      sort = !sort;
      steps = 0;
    }

    if(steps < arr.length && sort)
    {
      int threshold=10;

      for(int i=0;i<numbuckets;i++){
        //sort each bucket
        arrays[i]=sortbuckets(arrays[i],threshold,inArrays[i]);
        threshold=threshold+10;
      }
      steps++;
    }
    else if(steps == arr.length && sort)
    {
      return true;
    }


    return false;//returns array

  }


}

